#include <stdio.h>
#include <stdlib.h>
#define N 4  // 定义数组的大小
#define K 2  // 定义组合的大小

// 为实现回溯算法做前期准备的函数
void printCombination(int arr[], int n, int k);
// 实现用回溯算法解决组合问题的递归函数
void combinationUtil(int arr[], int data[], int start, int end, int index, int k);

int main() {
    int arr[N];  // 声明一个大小为 N 的数组

    // 初始化数组为 {1, 2, 3, 4}
    for (int i = 0; i < N; i++) {
        arr[i] = i + 1;
    }
    // 调用 printCombination 函数来打印所有可能的组合
    printCombination(arr, N, K);
    return 0;
}

// 用于初始化临时数组并开始组合过程
void printCombination(int arr[], int n, int k) {
    // 动态创建一个数组，用于存储选择了的元素
    int* data = (int*)malloc(k * sizeof(int));

    // 使用回溯生成所有组合
    combinationUtil(arr, data, 0, n, 0, k);

    free(data);  // 释放之前分配的内存
}

// 在 arr 数组中的[start,end)下标范围内，找到 k 个可选择的元素
// data[] 数组用于存储被选择了的元素
// index 参数用来统计被选择的元素个数
void combinationUtil(int arr[], int data[], int start, int end, int index, int k) {
    // 如果已找到一个完整的组合
    if (index == k) {
        // 打印当前组合
        for (int j = 0; j < k; j++) {
            printf("%d ", data[j]);
        }
        printf("\n");
        return;
    }

    // 递归生成所有可能的组合
    for (int i = start; (i < end) && (end - i + 1 >= k - index); i++) {
        data[index] = arr[i];  // 将当前元素加入到当前组合中
        combinationUtil(arr, data, i + 1, end, index + 1, k);  // 递归调用以选择下一个元素
    }
}